% !Mode:: "TeX:UTF-8"
\section{图像压缩}

\subsection{问题}

\begin{enumerate}
 \item 开发2-D离散余弦变换函数
 \item 使用离散余弦变换压缩图形并使用逆变换恢复图形
 \item 计算原图像和压缩图像的查图像
\end{enumerate}


\subsection[背景原理]{背景原理}
\subsubsection{离散余弦变换}

\begin{cdefi}
1-D 离散余弦变换(DCT)和其反变换由以下二式定义：
\begin{align}
C(u)&=a(u)\sum_{x=0}^{N-1}f(x)\cos\left[ \frac{(2x+1)u\pi}{2N} \right] \quad u=0,1,\ldots,N-1 \\
f(x)&=\sum_{u=0}^{N-1}a(u)C(u)\cos\left[ \frac{(2x+1)u\pi}{2N} \right] \quad x=0,1,\ldots,N-1
\end{align}
其中$a(u)$由下式定义：
$$
a(u)=\left\{
\begin{array}{l}
\sqrt{\frac{1}{N}} \quad \mbox{当$u=0$}\\
\sqrt{\frac{2}{N}} \quad \mbox{当$u=1,2,\ldots,N-1$}
\end{array}
\right.
$$
\end{cdefi}

\begin{cdefi}
2-D 离散余弦变换(DCT)和其反变换由以下二式定义：
\begin{align}
C(u,v)&=a(u)a(v) \sum_{x=0}^{N-1}\sum_{y=0}^{N-1}f(x,y) \cos\left[ \frac{(2x+1)u\pi}{2N} \right] \cos\left[ \frac{(2y+1)v\pi}{2N} \right]  \quad u,v=0,1,\ldots,N-1 \\
f(x,y)&=\sum_{u=0}^{N-1}\sum_{v=0}^{N-1} a(u)a(v) C(u,v) \cos\left[ \frac{(2x+1)u\pi}{2N} \right] \cos\left[ \frac{(2y+1)v\pi}{2N} \right]  \quad x,y=0,1,\ldots,N-1
\end{align}
\end{cdefi}


\subsubsection[离散余弦变换的快速算法]{离散余弦变换的实现\footnote{摘自《数字信号处理》胡广书著 清华大学出版社 2003}}

DCT和DFT有着密切的关系，它们都可以通过FFT来实现。可以用N点FFT来实现N点DCT计算。
定义：
\begin{equation}
\label{e:cdtf}
F(u)=\sum_{x=0}^{N-1}f(x)\cos\frac{(2x+1)u\pi}{2N} \quad u=0,1,\ldots,N-1
\end{equation}
可见$F(u)$和$C(u)$的差别只在于定标系数，现由$f(x)$构成一个新序列$g(x)$:
$$
\left\{
\begin{array}{l}
g(x)=f(2x)\\
g(N-1-x)=f(2x+1)
\end{array}
\right.
x=0,1,\ldots,N/2-1
$$
显然，$g(x)$的前$\frac{N}{2}$的点是$f(x)$中的偶数点。后一半是$f(x)$的奇数点，但次序要倒排。
这样式($\ref{e:cdtf}$)可以写成
\begin{equation}
F(u)=\sum_{x=0}^{N/2-1}g(x)\cos\frac{(4x+1)u\pi}{2N}+\sum_{x=0}^{N/2-1}g(N-1-x)\cos\frac{(4x+3)u\pi}{2N}
\end{equation}
对后一项作变量代换,令$y=N-1-x$,得
\begin{equation}
F(u)=\sum_{x=0}^{N/2-1}g(x)\cos\frac{(4x+1)u\pi}{2N}+\sum_{y=N/2}^{N-1}g(y)\cos\frac{(4y+1)u\pi}{2N}
\end{equation}
即
\begin{equation}
F(u)=\sum_{x=0}^{N-1}g(x)\cos\frac{(4x+1)u\pi}{2N}
\end{equation}
令
\begin{equation}
H(u)=e^{\frac{ju\pi}{2N}}\sum_{x=0}^{N-1}g(x)e^{-j\frac{2\pi}{N}xu}
\end{equation}
则
\begin{equation}
F(u)=Re\{H(u)\}
\end{equation}
将$F(u)$乘以定标因子，即得DCT $C(u)$。 这样，用N点的DFT可以实现N点DCT的快速计算。
\subsection{程序代码说明}

实际的1-D DCT代码参考了上节的原理，使用Numpy提供的FFT函数实现。2-D DCT变换函数的实现与FFT类似，也是通过调用一维函数来实现。

具体的DCT变换函数在文件 src/q6\_compression/dct.py 中。

有了DCT变换函数后，实现图像压缩就没有了困难。由于DCT变换后的主要信息都集中在了频谱一角，自然的可以想到将其余四分之三部分忽略掉，而图像没有很大损失。

另外，直接使用了OpenCV提供的DCT计算函数，用以相互比较结果。

\subsection{实验结果与分析}

\subsubsection{输出结果}
\begin{longtable}{ll}
\caption{边缘检测} \\
%\toprule
%\multicolumn{2}{c}{边缘检测} \\
%\midrule
%\endfirsthead
%\midrule
%\multicolumn{2}{c}{边缘检测} \\
%\midrule
\endhead
\midrule
\multicolumn{2}{r}{接下页\dots} \\
\endfoot
\endlastfoot
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{tabular}{l}
DCT变换  \\
\includegraphics[height=5cm]{../output/Q6_DCT_AMP.jpg}
\end{tabular}
&
\begin{tabular}{l}
用OpenCV进行的DCT变换 \\
\includegraphics[height=5cm]{../output/Q6_DCT_AMP_OPENCV.jpg}
\end{tabular}
\\
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{tabular}{l}
去$\frac{3}{4}$DCT后反变换的图像  \\
\includegraphics[height=5cm]{../output/Q6_DCT_Compression.jpg}
\end{tabular}
&
\begin{tabular}{l}
原图像与反变换的差图像 \\
\includegraphics[height=5cm]{../output/Q6_difference.jpg}
\end{tabular}
\\
\bottomrule
\end{longtable}

\subsubsection{结果分析}
通过输出结果，可以看到DCT变换结果与OpenCV系统计算得结果类似，主要区别仅为信息的分布位置不同。

与原图像比较，可以看到主要区别在于细节边缘，主要信息都保留完整。 

如果为了进一步提高压缩率和保证图像质量，可以通过对图像中的每一个$8\times8$小区域进行DCT变换，这样能在保证图像质量的前提下，进一步减少多余的信息。
同时也可以对DCT变换后的频率响应进行霍夫曼编码，进一步压缩图像。